package project3.dijkstra;

/**
 * 无向图
 * */

import edu.princeton.cs.algs4.*;
import project3.Point;

public class DijkstraSp1_2 {
    private double[] distTo;          // distTo[v] = distance  of shortest s->v path
    private Edge[] edgeTo;    // edgeTo[v] = last edge on shortest s->v path
    //private IndexMinPQ<Double> pq;    // priority queue of vertices
    private IndexMultiwayMinPQ<Double> pq;
    private Point[] points;
    private EdgeWeightedGraph mGraph;
    private int from;//源点
    private int to;//汇聚点

    public DijkstraSp1_2(EdgeWeightedGraph G, Point[] points) {
        this.points = points;
        mGraph = G;
        for (Edge e : G.edges()) {//判断有没有负边
            if (e.weight() < 0)
                throw new IllegalArgumentException("edge " + e + " has negative weight");
        }

        distTo = new double[G.V()];//源点到其他顶点的最短距离
        edgeTo = new Edge[G.V()];//



        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;

        // relax vertices in order of distance from s
        //pq = new IndexMinPQ<Double>(G.V());
        pq = new IndexMultiwayMinPQ<>(G.V(), 4);

    }

    public void setFrom(int from){
        initDijkstra();
        this.from = from;
        distTo[from] = 0.0;
        pq.insert(from,distTo[from]);
    }

    public void setTo(int to){
        this.to = to;
    }

    private void relax(Edge e,int v) {
        int w = e.other(v);
        /**
         * f(n)=g(n)+h(n)
         * A*算法
         *  d[v] + 从 v 到 w 的距离 + 从 w 到 d 的欧式距离 − 从 v 到 d 的欧式距离
         * */
        double weight = distTo[v] +
                        e.weight()+
                points[w].distanceTo(points[to]) -
                points[v].distanceTo(points[to]);;
        if (distTo[w] > weight) {
            distTo[w] = weight;
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else                pq.insert(w, distTo[w]);
        }
        //System.out.println("w:"+w+"dist["+w+"]:"+distTo[w]);
    }

    public double distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        while (!pq.isEmpty()){//想法1，发现最短路径就停止搜索
            int x = pq.delMin();
            if(x==v){
                return true;
            }
            for(Edge edge:mGraph.adj(x)) {
                relax(edge, x);
            }
        }
        return distTo[v]<Double.POSITIVE_INFINITY;
    }

    public void initDijkstra(){//初始化队列置空，
        for(int i = 0; i < mGraph.V(); i++){
            if (pq.contains(i)) pq.delete(i);
            if (edgeTo[i]!=null) edgeTo[i]=null;
            if(!Double.isInfinite(distTo[i])) distTo[i]=Double.POSITIVE_INFINITY;
        }
    }
    public Stack<Edge> pathTo(int v) {/**修改返回类型为栈*/
        if (!hasPathTo(v)) return null;
        Stack<Edge> path = new Stack<Edge>();
        int x = v;
        for (Edge e = edgeTo[v]; e != null; e = edgeTo[x]) {
            path.push(e);//从后往前入栈，再出栈即为路径
            x = e.other(x);
        }
        return path;
    }


}
